package com.gitee.feizns.explore.data_structure.linked_list.singly.partition;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/5
 */
public class Partition {

    public static void main(String[] args) {
        ListNode node = create();
        ListNode node1 = partition(node, 3);
        println(node1);
    }

    private static void println(ListNode tmp) {
        while ( tmp != null ) {
            System.out.print(tmp.val);
            tmp = tmp.next;
        }
    }

    private static ListNode create() {
        ListNode r = new ListNode(1);
        r.next = new ListNode(4);
        r.next.next = new ListNode(3);
        r.next.next.next = new ListNode(2);
        r.next.next.next.next = new ListNode(5);
        r.next.next.next.next.next = new ListNode(2);
        return r;
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode d1 = dummy1;
        ListNode d2 = dummy2;
        ListNode tmp = head;
        while ( tmp != null ) {
            if ( tmp.val < x ) {
                d1.next = tmp;
                d1 = tmp;
            } else {
                d2.next = tmp;
                d2 = tmp;
            }
            tmp = tmp.next;
        }
        d2.next = null;
        d1.next = dummy2.next;
        return dummy1.next;
    }

}
